1. Field
This application relates generally to computer graphics, and more specifically to computer systems and processes for efficiently rendering a scene, using out-of-core point-based global illumination.
2. Related Art
Global illumination is a technique used in computer graphics to add more realistic lighting to the scenes. One global illumination approach is known as the point-based global illumination (PBGI) approach. (See Per H. Christensen, “Point-based approximate color bleeding,” Pixar Technical Memo #08-01 (July 2008), hereinafter referred to as “Christensen 2008.”) PBGI generally involves solving for indirect illumination integrals and occlusion integrals. With PBGI, the directly illuminated geometry in the scene is represented by a point cloud representation, which is generated in a pre-computation phase prior to the rendering of the scene.
A point in a point cloud is a position in three-dimensional space containing energy information. In one example, a point may be a data representation of a surfel, which is a small circular disk-shaped surface element making up the different objects within a scene. As described in Christensen 2008, the surfaces of different objects are subdivided into small micropolygons, and the light energy emitting from each micropolygon (e.g., the radiance) is stored with each point. A point can also store other information, including a position, a surface normal, an effective area, a point-radius, and the like. As described in Christensen 2008, the effective area and the point-radius stored in a point are not the same thing; rather, they are two different representations of the size of the point. The point-radius circumscribes the micropolygon that the point represents. This ensures that the surfaces are completely covered by the points with no gaps in between. The effective area is the point's real area, which is smaller than the area corresponding to the point-radius.
To efficiently solve the illumination integrals with PBGI, the generated point cloud is further organized into a multi-resolution level-of-detail hierarchy. For example, an octree data structure may be used to partition the three-dimensional space represented by a point cloud by recursively subdividing the space into eight octants. An octree data structure is a tree data structure wherein each internal node has up to eight child nodes. Leaf nodes in the octree store the individual points of the point cloud and a point cluster for the volume of space the individual points in the leaf node cover. Each node other than a leaf node stores a point cluster, which is an approximation of a collection of points situated within a particular volume. For example, a point cluster representation includes an average position for the cluster, as well as the projected area and emitted energy when the cluster is viewed from various directions (the directional projected area and directional emitted energy, respectively).
After generating the octree hierarchy, both the full point cloud and the octree hierarchy may then be used to compute the indirect illumination integrals and occlusion integrals at all the “shading locations” seen from a virtual camera. However, not all the nodes of the octree are necessary to compute the integrals at a particular shading location. For example, when an object is far away from a shading location in the scene, less refined nodes of the octree may be used to calculate the various integrals. When an object is close by, more refined nodes or even individual points may be used. However, using more refined nodes to compute the integrals translates to longer shading time.
The octree clustering technique described above reduces the complexity of solving the actual integrals significantly. Nevertheless, the amount of execution time required by the algorithm used to build the octree clustering has a complexity order of at least O(n log n) and the amount of memory required to store the aforementioned data structures has a complexity order of at least O(n), where n is the number of input points in the point cloud. Further, PBGI is used in production to render complex scenes, so storage of the points in the point cloud and octree data structure in main memory (or resident memory on a machine) quickly becomes a constraining factor on the number of points in the point cloud.
Rendered images used in high-quality motion pictures need to be photorealistic. One way to increase photorealism is to increase the number of points in the point cloud. However, as discussed, the number of points is limited by the amount of main (in-core) memory available. Therefore, a technique is required that utilizes constrained amounts of memory, while allowing for increased numbers of points in the point cloud.